#leetcode题目93：复原IP地址
#难度：中等

class Solution:
    def restoreIpAddresses(self, s: str) -> list:
        if len(s)<4:
            return []
        def dfs(ip, idx):
            if len(ip) == 4 and idx == len(s):
                res.append('.'.join(ip))
                return
            for i in range(1,4):
                if idx + i > len(s):
                    continue
                sub = s[idx:idx+i]
                if len(sub) > 1 and sub[0] == '0':
                    continue
                if int(sub) > 255:
                    continue
                ip.append(sub)
                dfs(ip, idx+i)
                ip.pop()
        res = []
        dfs([],0)
        return res


#测试数据
s = "25525511135"
#预期输出：["255.255.11.135","255.255.111.35"]
solution = Solution()
print(solution.restoreIpAddresses(s))

s = "0000"
#预期输出：["0.0.0.0"]
solution = Solution()
print(solution.restoreIpAddresses(s))

s = "101023"
#预期输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
solution = Solution()
print(solution.restoreIpAddresses(s))
